import java.net.MalformedURLException;
import java.util.Arrays;

/**
 * Created by L.jp
 * Description:
 * User: 86189
 * Date: 2022-07-10
 * Time: 18:21
 */
//二分法
    //1.有序数组中找到num
    //2.有序数组中找到>=num最左的位置
    //3.有序数组中找到<=num最右的位置
    //4.局部最小值问题
public class BinarySearch {
    //1.有序数组中找到num
    public  static boolean find(int[] arr,int num){
        int l=0;
        int r=arr.length-1;
        while ( l<=r ){
            int m=(l+r)/2;
            if(arr[m]==num){
                return true;
            }else if(arr[m]<num){
                l=m+1;
            }else{
                r=m-1;
            }
        }
        return false;
    }
    //对比的测试方法
    public static boolean test1(int[] arr,int num){
        for(int n :arr){
            if(n==num){
                return true;
            }
        }
        return false;
    }
    
    //对数器，随机生成数组
    public static int[] generateArr(int maxlen,int maxval){
        int len=(int) (Math.random() *(maxlen+1));
        int[] arr=new int[len];
        for(int i = 0; i < len; i++){
            arr[i]=(int) ((maxval+1)*Math.random())-(int)(maxval*Math.random());
        }
        return arr;
    }
    //2.有序数组中找到>=num最左的位置
    public static int mostLeftIndex(int [] arr,int num){
        int l=0;
        int r=arr.length-1;
        int ans=-1; //记录最左边的位置
        while ( l<=r ){
            int m=(l+r)/2;
            if(arr[m]>=num){
                ans=m;
                r=m-1;
            }else{
                l=m+1;
            }
        }
        return ans;
    }
    //另一个方法
    public static  int test2(int [] arr,int num){
        for(int i=0;i<arr.length; i++){
            if(arr[i] >= num){
                return i;
            }
        }
        return -1;
    }
    
    //4.局部最小值问题
    /*局部最小值定义：假设有长度为n的数组arr，如果0下标的数小于1下标的数，那么0下标的数就是局部最小值
    * 如果arr[n-1] < arr[n-2],那么arr[n-1]就是局部最小值
    * 如果arr[i]<arr[i-1] && arr[i]<arr[i+1]那么arr[i]就是局部最小值*/
    /*如果这些都不满足，那么就说明0~1是递减的，n-2~n-1是递增的，所以0~n-1必定存在一个局部最小值
    * 这些情况可以适用于任何一个区间，所以我们可以利用二分法找到这个局部最小值*/
    public static int arrayLocalMinimum(int[] arr){
        //这里返回的是局部最小值的下标
        if(arr==null || arr.length == 0) {
            return -1;
        }
        int n=arr.length;
        if(n==1){
            return 0;
        }
        if(arr[0]<arr[1]){
            return 0;
        }
        if(arr[n-2]>arr[n-1]){
            return n-1;
        }
        //如果上述都不满足，那么接下来就是在中间的情况
        int l=0;
        int r=n-1;
        //当满足l,r区间范围缩小到有三个数才进行判断，否则只有两个，返回其中一个比较小的即可
        //使l<r-1也可以始终保证m-1和m+1是合法的下标
        while ( l<r-1){
            int m=(l+r)/2;
            //如果arr[i]<arr[i-1] && arr[i]<arr[i+1]那么arr[i]就是局部最小值
            if(arr[m]<arr[m-1] && arr[m]<arr[m+1]){
                return m;
            }else{
                //否则要么是
                //①左>中>右
                //②左<中<右
                //③左<中，中>右
                //那么无非就是左>中，左<中的情况，所以局部最小值就可以使用二分法
                if(arr[m-1]>arr[m]){
                    // 左>中,那么局部最小值就是在mid右边
                    l=m+1;
                }else{
                    //左<中,那么局部最小值就是在mid左边
                    r=m-1;
                }
            }
        }
        //否则范围缩小到就剩下两个数，就直接找出谁最小
        return arr[l]>arr[r] ? r: l;
    }
    
    //生成一个随机数组且相邻不相等的对数器
    public static int[] generateArray(int maxlen,int maxval){
        int len=(int) (Math.random() * maxlen);
        int[] arr=new int[len];
        if(len>0) {
            arr[0] = (int) (Math.random() * maxval);
            for(int i=1;i<len; i++){
                do{
                    arr[i] = (int) (Math.random() * maxval);
                }while ( arr[i-1]==arr[i] );
            }
        }
        return arr;
        
    }
    //用于测试,看我们写的方法得到的局部最小值是不是局部最小值
    public static boolean test3(int[] arr,int minIndex){
        if(arr.length==0){
            return minIndex==-1;
        }
        int left=minIndex-1;
        int right=minIndex+1;
        boolean leftBigger=left>=0 ? arr[left] >arr[minIndex] :true; //如果left==-1,说明minIndex就是局部最最小值的下标，否则就看是不是左边值大
        boolean rightBigger=right<arr.length ? arr[right]>arr[minIndex] : true;//如果right超出数组范围,说明minIndex就是局部最最小值的下标，否则就看是不是右边值大
        return leftBigger && rightBigger; //如果左>中，中<右，那么minIndex就是局部最小值
    }
    public static void printArray(int[] arr) {
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
    
    //打印
    public static void main (String[] args) {
        int maxLen = 100;
        int maxValue = 200;
        int testTime = 1000000;
        System.out.println("测试开始");
        for (int i = 0; i < testTime; i++) {
            int[] arr = generateArray(maxLen, maxValue);
            int ans = arrayLocalMinimum(arr);
            if (!test3(arr, ans)) {
                printArray(arr);
                System.out.println(ans);
                break;
            }
        }
        System.out.println("测试结束");
    }
    
//    public static void main (String[] args) {
//        int maxlen=10;
//        int maxval=100;
//        int testTimes=20;
//        boolean succeed=true;
//        for(int i=0;i<testTimes;i++){
//            int[] arr=generateArr( maxlen,maxval );
//            Arrays.sort(arr);
//            //如果maxval是100，那么随机生成的val就是-99~100的整数
//            int val=(int) ((maxval+1)*Math.random())-(int)(maxval*Math.random());
//            System.out.println(val);
//            //比较两个方法
//            if(test2( arr,val )!=mostLeftIndex( arr,val )){
//                System.out.println("出错了！");
//                succeed=false;
//                break;
//            }
//        }
//        System.out.println(succeed ? "Nice!" : "No good!");
//    }

    
}
